package lru

import "fmt"

type LRUCache struct {
	cap   int // 容量
	count int // 当前数量
	head  *LRUNode
	tail  *LRUNode
	cmap  map[string]*LRUNode
}

type LRUNode struct {
	key   string
	value any
	pre   *LRUNode
	next  *LRUNode
}

func NewLRUCache(cap int) *LRUCache {
	if cap <= 0 {
		panic("cap must be greater than 0")
	}
	return &LRUCache{
		cap:   cap,
		count: 0,
		head:  nil,
		tail:  nil,
		cmap:  make(map[string]*LRUNode),
	}
}

func (lru *LRUCache) addHead(node *LRUNode) {
	node.next = lru.head
	node.pre = nil
	if lru.head != nil {
		lru.head.pre = node
	}
	lru.head = node
	if lru.tail == nil {
		lru.tail = node
	}
	lru.cmap[node.key] = node
	lru.count++
}

func (lru *LRUCache) removeNode(node *LRUNode) {
	if node.pre != nil {
		node.pre.next = node.next
	} else {
		lru.head = node.next
	}
	if node.next != nil {
		node.next.pre = node.pre
	} else {
		lru.tail = node.pre
	}
	delete(lru.cmap, node.key)
	lru.count--
}

func (lru *LRUCache) moveToHead(node *LRUNode) {
	if node == lru.head {
		return
	}
	lru.removeNode(node)
	lru.addHead(node)
}

func (lru *LRUCache) removeTail() {
	if lru.tail != nil {
		delete(lru.cmap, lru.tail.key)
		lru.count--
		if lru.head == lru.tail {
			lru.head = nil
			lru.tail = nil
		} else {
			lru.tail = lru.tail.pre
			lru.tail.next = nil
		}
	}
}

func (lru *LRUCache) Get(key string) (any, bool) {
	if node, ok := lru.cmap[key]; ok {
		lru.moveToHead(node)
		return node.value, true
	}
	return nil, false
}

func (lru *LRUCache) Put(key string, value any) {
	if node, ok := lru.cmap[key]; ok {
		node.value = value
		lru.moveToHead(node)
	} else {
		node := &LRUNode{
			key:   key,
			value: value,
		}
		lru.addHead(node)
		if lru.count > lru.cap {
			lru.removeTail()
		}
	}
}

func (lru *LRUCache) Len() int {
	return lru.count
}

func (lru *LRUCache) Cap() int {
	return lru.cap
}

func (lru *LRUCache) print() {
	fmt.Println("LRU Cache: **********")
	node := lru.head
	for node != nil {
		fmt.Printf("%s:%v|", node.key, node.value)
		node = node.next
	}
	fmt.Println("\n**********")
}
